//矩阵中的最长递增路径
class Solution {
public:
    int srci , srcj , m , n , maxlen;
    int path[201][201];//记录[srci,srcj]为起点的的最长递增路径
    int dx[4] = {0,0,-1,1} , dy[4] = {-1,1,0,0};
    int dfs(vector<vector<int>>& matrix , int row , int col)
    {
        if(path[row][col] != 0) return path[row][col];
        int ret = 1;
        for(int i = 0 ; i < 4 ; ++i)
        {
            int x = col + dx[i] , y = row + dy[i];
            if(x >= 0 && y >= 0 && x < m && y < n && matrix[y][x] > matrix[row][col])
            {
                ret = max(ret,dfs(matrix,y,x)+1);
            }
        }
        path[row][col] = ret;
        return ret;
    }
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix[0].size() , n = matrix.size();
        int ret = 0;
        for(int i = 0 ; i < n ; ++i)
        {
            for(int j = 0 ; j < m ; ++j)
            {
                srci = i , srcj = j;
                ret = max(ret,dfs(matrix,srci,srcj));
                //dfs帮我找到以[srci,srcj]为起点的最长递增路径
            }
        }
        return ret;
    }
};

//猜数字大小Ⅱ
class Solution {
public:
    int n;
    int root[201][201];
    int dfs(int left,int right)
    {
        if(left >= right) return 0;
        if(root[left][right] != 0) return root[left][right];
        int ret = INT_MAX;
        for(int i = left ; i <= right ; ++i)
        {
            ret = min(ret,max(dfs(left,i-1),dfs(i+1,right)) + i);
        }
        root[left][right] = ret;
        return ret;
    }
    int getMoneyAmount(int _n) {
        n = _n;
        return dfs(1,_n);
    }
};

//最长递增子序列
class Solution {
public:
    vector<int> dp;
    int dfs(vector<int>& nums , int pos)
    {
        if(dp[pos] != 0) return dp[pos];
        if(pos == nums.size()) return 0;
        int ret = 0;
        int val = nums[pos];
        for(int i = pos+1 ; i < nums.size() ; ++i)
            if(nums[i] > val)
                ret = max(dfs(nums,i)+1 , ret);

        dp[pos] = ret;
        return ret;
    }   
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        dp.resize(n);
        int ret = 0;
        for(int i = 0 ; i < n ; ++i)
            ret = max(dfs(nums,i)+1,ret);
        return ret;
    }
};

//不同路径
class Solution {
public:
    int dp[101][101];
    int dfs(int m , int n)
    {
        if(m == 0 || n == 0) return 0;
        if(dp[m][n] != -1)
        {
            return dp[m][n];
        }
        dp[m][n] = dfs(m-1,n) + dfs(m,n-1);
        return dp[m][n];
    }
    int uniquePaths(int m, int n) {
      memset(dp,-1,sizeof(dp));
      dp[1][1] = 1;
      return dfs(m,n);
    }
};

//斐波那契数列
class Solution {
public:
    const static int num = 1000000007;
    int dp[101];
    int dfs(int n)
    {
        if(n == 0 || n == 1) return n;
        if(dp[n] != 0)
        {
            return dp[n];
        }
        dp[n] = ((dfs(n-1) % num) + (dfs(n-2) % num)) % num;
        return dp[n];
    }
    int fib(int n) {
         return dfs(n);
    }
};